동적 배열

배열의 단점인 '고정된 크기'를 해결한 배열.
배열이 다 차면 두 백의 크기의 새 배열을 만들고, 기존의 변수들을 복사해서 넣는다.
마찬가지로 배열의 공간이 반 이상 남으면 배열의 크기를 반으로 줄인다.

연결 리스트

• 장점. 상수 시간 안에 확장 가능
  위에서 설명한 동적 배열도 확장은 가능하지만 원래 배열의 크기에 따라 확장하는데 시간이 더 오래 걸린다. n크기의 배열을 확장(원래 변수들을 복사)하는데 O(n)만큼의 시간이 걸린다.
  그러나 연결 리스트는 새로운 새로운 변수를 메모리에 추가하는 시간만 필요하니까 항상 일정한 시간만 소요된다.
• 단점. 개별 항목에 접근하는 시간이 길다.
  pint(myArray[300])이라고 하면 배열의 기본 주소에 offset(size * index)를 더하는 간단한 계산으로 바로 해당 변수를 가져올 수 있다.
  그러나 print(myLinkedList[300])이라고 하면 0번째 -> 1번째 -> 2번째 -> .... 이렇게 299번째의 포인터를 읽고 해당 주소를 가져오게 되는것. O(n)의 시간이 걸린다.

  배열의 locality
  cpu의 계산속도가 메모리가 cpu로 데이터를 전송하는 속도보다 월등히 빠르기 때문에 cpu 안에 있는 cache영역(메모리보다 훨씬 빠르다)에 메모리가 데이터를 전달하고 cpu는 거기서 연산할 자료들을 가져온다.
  그런데 링크드 리스트처럼 요소들이 흩어져 있는 경우 메모리에서 캐시로 가져갈 때 멀리있는건 빼놓고 전달할 수 있고(missing 한다고 표현) 그렇게 되면 연산 속도가 느려진다.

• 단점. 추가적인 참조 포인터를 위한 메모리 공간 낭비
  (값/포이터) -> (값/포인터) -> .... 이렇게 생겼기 때문에 포인터를 위한 공간이 필요하다는 것.

Singly Linked List

일반적인 '링크드 리스트'는 주로 이걸 지칭한다.
head -> (값/포인터) -> (값/포인터) -> .... -> (값/null)

삽입

head->7->14->25->36 처럼 오름차순으로 정렬된 숫자를 담고있는 리스트가 있다.

맨 앞에

3을 넣으려면 맨 앞에 넣어야한다.

1. 새 노드 (3 노드)를 만들고
2. 7 노드를 가리키는 헤더를 3을 가리키도록 바꾸고
3. 3 노드가 7 노드를 가리키게 한다. 이 방법이면 충분한것 처럼 보이나. 2번 단계에서 헤드가 7 노드 대신 3노드를 가리키면서 7 노드의 주소값은 아무도 모르게 된다. 그래서 3 노드가 가리킬 주소를 몰라서 3번 단계가 불가능하다. 그래서 다음과 같이 진행해야한다.
4. 새 노드(3 노드)를 만들고
5. 3노드가 7노드를 가리키게 하고
6. 헤드가 7 대신 3 노드를 가리키게 해야한다.
   (위의 2번과 3번의 순서를 바꾼다.)

맨 뒤에

50을 너으려면 맨 뒤에 넣어야한다.

1. 새 노드(50 노드)를 만든다.
2. 포인터가 null인 36 노드에 도착.
3. 36 노드의 포인터에 null이 아닌 50 노드의 주소값을 입력.

중간에

20이라느 숫자는 14와 25사이에 위치해야한다.
이 경우는 사실 위에서 본 맨 앞에 삽입하는것과 동일하다.

1. 새 노드(20)을 만들고
2. 20 노드가 25 노드를 가리키게 하고
3. 14 노드가 20 노드를 가리키게 해야한다. 마찬가지로 14노드가 25노드를 가리키는 포인터의 값을 바꾸면 25 주소값은 프로그램상에서 사라지기 때문에 먼저 20노드가 25를 가리키도록 해야한다.

코드 예시

수업중에는 c언어를 사용해 설명하시는데 그걸 굳이 받아 적지는 않겠다.

c언어는 call by value
void swap(int a, int b){...}라는 함수를 호출하면서 swap(p,q)라고 호출하면 p와 q의 주소값을 전달하지 않고 실제 p와 q의 값(숫자)를 복사해서 준다.
swap() 함수의 목적이 p와 q의 값을 서로 바꿔서 반환하는 것이라면 그걸 호출한 상위 함수에서는 매개변수 p와 q의 포인터를 전달해야 한다.

새로운 노드를 삽입하는 Insert() 함수를 만드려면 포인터를 사용해야 한다.
왜?
맨 앞에 넣는다고 가정해보면, 헤드가 가지고 있는 포인터의 값을 새 노드의 주소값으로 바꿔줘야 하기 때문에. 포인터가 아닌 그냥 주소값 자체를 건내주면 새 노드가 기존 노드를 가리키게 할 수는 있겠지만 헤드가 자신을 가리키게 만들 방법이 없다.